package algorithm;

import java.util.Arrays;

/**
 * 189. 旋转数组
 * @author Panbo Guo
 * @date 2021/7/8
 */
public class T00189 {

    public static void main(String[] args) {
        int[] nums = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
        new Solution().rotate(nums, 12);
        System.out.println(Arrays.toString(nums));
    }

    static class Solution {

        public void rotate(int[] nums, int k) {
            if (nums.length == 1) {
                return;
            }
            final int length = nums.length;
            if (k > length) {
                k = k % length;
            }
            if (k == length) {
                return;
            }
            int mid = length - k;
            if (mid > k) {
                int[] arr = new int[k];
                System.arraycopy(nums, mid, arr, 0, k);
                System.arraycopy(nums, 0, nums, k, mid);
                System.arraycopy(arr, 0, nums, 0, k);
            } else {
                int[] arr = new int[mid];
                System.arraycopy(nums, 0, arr, 0, mid);
                System.arraycopy(nums, mid, nums, 0, k);
                System.arraycopy(arr, 0, nums, k, mid);
            }
        }

//        public void rotate(int[] nums, int k) {
//            if (nums.length == 1) {
//                return;
//            }
//            final int length = nums.length;
//            if (k > length) {
//                k = k % length;
//            }
//            if (k == length) {
//                return;
//            }
//            if (length - k == k) {
//                // 两边相等，交换两侧的元素
//                sweep(nums, 0, length - 1, k);
//            } else if (length - k < k){
//                // 左边小，左旋
//                leftRoll(nums, length - 1, 0, length - k);
//            } else {
//                // 右边小，右旋
//                rightRoll(nums, 0, length - 1, k);
//            }
//        }
//
//        private void sweep(int[] nums, int s, int e, int k) {
//            final int limit = s + k;
//            for (int i = s, j = limit; ;) {
//                if (i >= limit) {
//                    break;
//                }
//                int t = nums[j];
//                nums[j] = nums[i];
//                nums[i] = t;
//                i ++;
//                j ++;
//            }
//        }
//
//        private void rightRoll(int[] nums, int s, int e, int k) {
//            if (e <= s || k == 0) {
//                return;
//            }
//            if (e - s == 1) {
//                int t = nums[e];
//                nums[e] = nums[s];
//                nums[s] = t;
//                return;
//            }
//            final int limit = e - k + 1;
//            for (int i = s, j = i + k, p = limit; ;) {
//                if (p <= e) {
//                    int t = nums[j];
//                    nums[j] = nums[i];
//                    nums[i] = nums[p];
//                    nums[p] = t;
//                    p ++;
//                    i ++;
//                    j ++;
//                } else {
//                    if (j < limit) {
//                        if (limit - j == k) {
//                            sweep(nums, j, e, k);
//                        } else if (limit - j > k) {
//                            rightRoll(nums, j, e, k);
//                        } else {
//                            leftRoll(nums, e, j, limit - j);
//                        }
//                    } else if (j < e){
//                        if (e - j == 1) {
//                            if (((e - s) & 0b1) == 0) {
//                                sweep(nums, j, e, 1);
//                            }
//                        } else if (j != limit){
//                            int m = e - ((j - limit) % (e - j));
//                            if (e - m == 0 || (m - j == e - m && e - s % 2 == 0)) {
//                                sweep(nums, j, e, m - j);
//                            } else if (m - j > e - m) {
//                                rightRoll(nums, j, e, e - m);
//                            } else {
//                                leftRoll(nums, e, j, m - j);
//                            }
//                        }
//                    }
//                    break;
//                }
//            }
//        }
//
//        private void leftRoll(int[] nums, int s, int e, int k) {
//            if (e >= s || k == 0) {
//                return;
//            }
//            if (s - e == 1) {
//                int t = nums[e];
//                nums[e] = nums[s];
//                nums[s] = t;
//                return;
//            }
//            final int limit = e + k - 1;
//            for (int i = s, j = i - k, p = limit; ;) {
//                if (p >= e) {
//                    int t = nums[j];
//                    nums[j] = nums[i];
//                    nums[i] = nums[p];
//                    nums[p] = t;
//                    p --;
//                    i --;
//                    j --;
//                } else {
//                    if (j > limit) {
//                        if (j - limit == k) {
//                            sweep(nums, e, j, k);
//                        } else if (j - limit > k) {
//                            leftRoll(nums, j, e, k);
//                        } else {
//                            rightRoll(nums, e, j, limit - j);
//                        }
//                    } else if (j > e){
//                        if (j - e == 1) {
//                            if (((s - e) & 0b1) == 0) {
//                                sweep(nums, e, j, 1);
//                            }
//                        } else if (j != limit){
//                            int m = e + ((limit - j) % (j - e + 1));
//                            if (m - e == 0 || (m - e == j - m && j - e % 2 == 0) ) {
//                                sweep(nums, e, j, j - m);
//                            } else if (m - e > j - m) {
//                                rightRoll(nums, e, j, j - m);
//                            } else {
//                                leftRoll(nums, j, e, m - e);
//                            }
//                        }
//                    }
//                    break;
//                }
//            }
//        }
    }
}
